package com.jxmobi.util.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * Search target bytes(byte[]) from source bytes(byte[])<br>
 * <br>
 * This class is going to scan byte[] data to sequential, it is effective in
 * small size(less than 1kBytes) byte[] data.<br>
 *
 * @author Xiaofei Chen <a href="mailto:neocxf@qq.com">Email the author</a>
 * @version 1.0 12/21/2015
 */
public class BinarySearcher {

	/**
	 * Returns the index within this byte-array of the first occurrence of the
	 * specified(search bytes) byte array.<br>
	 * 
	 * @param srcBytes
	 * @param searchBytes
	 * @return
	 */
	public int indexOf(byte[] srcBytes, byte[] searchBytes) {
		final int startIndex = 0;
		final int endIndex = srcBytes.length - 1;
		return indexOf(srcBytes, searchBytes, startIndex, endIndex);
	}

	/**
	 * Returns the index within this byte-array of the first occurrence of the
	 * specified(search bytes) byte array.<br>
	 * Starting the search at the specified index<br>
	 * 
	 * @param srcBytes
	 * @param searchBytes
	 * @param startIndex
	 * @return
	 */
	public int indexOf(byte[] srcBytes, byte[] searchBytes, int startIndex) {
		final int endIndex = srcBytes.length - 1;
		return indexOf(srcBytes, searchBytes, startIndex, endIndex);
	}

	/**
	 * Returns the index within this byte-array of the first occurrence of the
	 * specified(search bytes) byte array.<br>
	 * Starting the search at the specified index, and end at the specified
	 * index.
	 * 
	 * @param srcBytes
	 * @param searchBytes
	 * @param startIndex
	 * @param endIndex
	 * @return
	 */
	public int indexOf(byte[] srcBytes, byte[] searchBytes, int startIndex, int endIndex) {

		if (searchBytes.length == 0 || (endIndex - startIndex + 1) < searchBytes.length) {

			return -1;
		}

		int maxScanStartPosIdx = srcBytes.length - searchBytes.length;

		final int loopEndIdx;

		if (endIndex < maxScanStartPosIdx) {
			loopEndIdx = endIndex;
		} else {
			loopEndIdx = maxScanStartPosIdx;
		}

		int lastScanIdx = -1;

		label: // goto label
		for (int i = startIndex; i <= loopEndIdx; i++) {

			for (int j = 0; j < searchBytes.length; j++) {

				if (srcBytes[i + j] != searchBytes[j]) {
					continue label;
				}

				lastScanIdx = i + j;

			}

			if (endIndex < lastScanIdx || lastScanIdx - i + 1 < searchBytes.length) {
				// it becomes more than the last index
				// or less than the number of search bytes
				return -1;
			}

			return i;
		}
		return -1;
	}

	/**
	 * Search bytes in byte array returns indexes within this byte-array of all
	 * occurrences of the specified(search bytes) byte array.
	 * 
	 * @param srcBytes
	 * @param searchBytes
	 * @return result index list
	 */
	public List<Integer> searchBytes(byte[] srcBytes, byte[] searchBytes) {
		final int startIdx = 0;
		final int endIdx = srcBytes.length - 1;
		return searchBytes(srcBytes, searchBytes, startIdx, endIdx);
	}

	public List<Integer> searchBytes(byte[] srcBytes, byte[] searchBytes, int searchStartIndex) {
		int endIdx = srcBytes.length - 1;
		return searchBytes(srcBytes, searchBytes, searchStartIndex, endIdx);
	}

	/**
	 * Search bytes in byte array returns indexes within this byte-array of all
	 * occurrences of the specified(search bytes) byte array in the specified
	 * range
	 * 
	 * @param srcBytes
	 * @param searchBytes
	 * @param searchStartIndex
	 * @param searchEndIndex
	 * @return result index list
	 */
	public List<Integer> searchBytes(byte[] srcBytes, byte[] searchBytes, int searchStartIndex, int searchEndIndex) {
		final int destSize = searchBytes.length;

		final List<Integer> positionIndexList = new ArrayList<Integer>();

		int cursor = searchStartIndex;

		while (cursor < searchEndIndex + 1) {

			int index = indexOf(srcBytes, searchBytes, cursor, searchEndIndex);

			if (index >= 0) {

				positionIndexList.add(index);
				cursor = index + destSize;

				// just return, if you want all the index, then you should comment the following clause
				break;
			} else {
				cursor++;
			}
		}
		return positionIndexList;
	}

}